#include <vector>
#include <map>

using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        
        int mid = (len1+len2) / 2;
        int left1 = 0;
        int left2 = 0;
        int pre = 0;
        while((left1<len1 || left2<len2) && left1+left2<mid)
        {
            if(left1==len1 || left2<len2 && nums2[left2]<nums1[left1])
            {
                pre = nums2[left2];
                left2++;
            }
            else
            {
                pre = nums1[left1];
                left1++;
            }
        }
        int cnt_val = left1==len1 && left2==len2 ? 0 :
                (left1==len1 ? nums2[left2] :
                (left2==len2 ? nums1[left1] : min(nums2[left2], nums1[left1])));
        return (len1+len2)%2 ? cnt_val : (cnt_val+pre)/2.0;
    }
};

// O(logn)
class Solution {
public:
    double getMedian(vector<int>& nums1, vector<int>& nums2, int k)
    {
        int m = nums1.size();
        int n = nums2.size();
        int first1 = 0;
        int first2 = 0;
        while(true)
        {
            if(first1 == m)
                return nums2[first2+k-1];
            if(first2 == n)
                return nums1[first1+k-1];
            if(k == 1)
                return min(nums1[first1], nums2[first2]);

            int cntFirst1 = min(m-1, first1+k/2-1);
            int cntFirst2 = min(n-1, first2+k/2-1);

            if(nums1[cntFirst1] <= nums2[cntFirst2])
            {
                k = k - (cntFirst1 - first1 + 1);
                first1 = cntFirst1 + 1;
            }
            else
            {
                k = k - (cntFirst2 - first2 + 1);
                first2 = cntFirst2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int len = m + n;
        if(len % 2 == 1)
            return getMedian(nums1, nums2, (len+1)/2);
        else
            return (getMedian(nums1, nums2, len/2)+getMedian(nums1, nums2, len/2+1))/2.0;
    }
};